package com.leetcodehot.problems;

public class problemsLCP51 {
    /**
     * 题目说明每种料理只能制作一次，那就是选与不选
     */
    private int maxX = -1;
    private int x = 0;
    private int y = 0;

    public int perfectMenu(int[] materials, int[][] cookbooks, int[][] attribute, int limit) {
        int n = cookbooks.length;

        dfs(materials, cookbooks, attribute, limit, 0, n);
        return maxX;
    }

    private void dfs(int[] materials, int[][] cookbooks, int[][] attribute, int limit, int i, int n) {
        if (i == n) {
            if (limit <= y) {
                maxX = Math.max(maxX, x);
            }
            return;
        }
        //不做
        dfs(materials, cookbooks, attribute, limit, i + 1, n);

        //做
        if (enough(i, materials, cookbooks)) {
            for (int j = 0; j < cookbooks[0].length; j++) {
                materials[j] -= cookbooks[i][j];
            }
            x += attribute[i][0];
            y += attribute[i][1];
            dfs(materials, cookbooks, attribute, limit, i + 1, n);
            for (int j = 0; j < cookbooks[0].length; j++) {
                materials[j] += cookbooks[i][j];
            }
            x -= attribute[i][0];
            y -= attribute[i][1];
        }
    }

    private boolean enough(int i, int[] materials, int[][] cookbooks) {
        for (int j = 0; j < cookbooks[0].length; j++) {
            if (materials[j] < cookbooks[i][j]) {
                return false;
            }
        }
        return true;
    }
}
